package leetcode

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// Input: nums = [3,2,1,6,0,5]
// Output: [6,3,5,null,2,0,null,null,1]
// https://leetcode.com/problems/maximum-binary-tree/
func constructMaximumBinaryTree(nums []int) *TreeNode {
	stack := []*TreeNode{}
	for _, v := range nums {
		node := &TreeNode{Val: v}
		var last *TreeNode = nil
		for len(stack) > 0 && stack[len(stack)-1].Val < v {
			last = stack[len(stack)-1]
			stack = stack[0 : len(stack)-1]
		}
		node.Left = last
		if len(stack) > 0 {
			stack[len(stack)-1].Right = node
		}
		stack = append(stack, node)
	}
	return stack[0]
}

func constructMaximumBinaryTree2(nums []int) *TreeNode {
	if len(nums) < 1 {
		return nil
	}
	value, index := math.MinInt, -1
	for i, v := range nums {
		if value < v {
			value = v
			index = i
		}
	}
	root := &TreeNode{Val: value}
	root.Left = constructMaximumBinaryTree2(nums[0:index])
	root.Right = constructMaximumBinaryTree2(nums[index+1:])
	return root
}
